package com.leetcode.algorithm.y22.m08.w3;

import java.util.ArrayList;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 501. 二叉搜索树中的众数
 * 
 * https://leetcode.cn/problems/find-mode-in-binary-search-tree/
 * 
 * @author jie.deng
 *
 */
class Question0501Solution01 {

	public int[] findMode(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		findMode(root, result, new TreeNode[] { null }, new int[] { 0 }, new int[] { 0 });
		return result.stream().mapToInt(Integer::intValue).toArray();
	}

	/**
	 * 
	 * @param cur
	 * @param result    众数
	 * @param prevNodes 前一个节点的引用
	 * @param prevCnt   前一个节点个数的引用
	 * @param maxCnts   众数个数的引用
	 */
	private void findMode(TreeNode cur, List<Integer> result, TreeNode[] prevNodes, int[] prevCnts, int[] maxCnts) {
		if (cur == null) {
			return;
		}
		findMode(cur.left, result, prevNodes, prevCnts, maxCnts);

		if (prevNodes[0] != null && prevNodes[0].val == cur.val) {
			prevCnts[0]++;
		} else {
			prevNodes[0] = cur;
			prevCnts[0] = 1;
		}
		if (prevCnts[0] == maxCnts[0]) {
			result.add(cur.val);
		} else if (prevCnts[0] > maxCnts[0]) {
			result.clear();
			result.add(cur.val);
			maxCnts[0] = prevCnts[0];
		}

		findMode(cur.right, result, prevNodes, prevCnts, maxCnts);
	}

}